L (сложеност)
У рачунарској теорији сложености, L (позната и као LSPACE или DLOGSPACE) је класа сложености која садржи проблеме одлучивости, који могу да буду решени помоћу детерминистичке Тјурингове машине која користи логаритамску количину меморијског простора.[1][2] Логаритамски простор је довољан да прихвати константан број показивача на улазе и логаритамски број логичких – Булових вредности. Многи основни logspace (логаритамски простор) алгоритми користе меморију на исти начин.
Комплетни проблеми и логичка карактеризација
[уреди | уреди извор]Сваки нетривијални проблем из L је комплетан применом logspace свођења[3]. Тако су мања свођења довољна да би се идентификовали смислени појмови L – комплетности. Најчешћа је употреба свођења првог реда.
Rезултати Омера Рајнголда из 2004. године показују да је USTCON (проблем да ли постоји путања између два чвора у задатом неусмереном графу) у L, и при томе, да је L = SL, пошто је USTCON SL – комплетан.
Једна последица тога је једноставна логичка карактеризација L: L садржи само језике који се могу описати логиком првог реда са додатним кумулативним оператором транзитивног затварања ( у смислу теорије графова, ово сваку повезану компоненту претвара у клику). Овај резултат има следећу примену у језицима за упите у базама података : сложеност података упита је дефинисана као сложеност одговарања на фиксни упит, при чему се дужина података посматра као улазна променљива. Узимајући у обзир ову дефииницију, упити над релационим базама података са комплетном информацијом ( не узимајући у обзир вредности nulls – празна поља) , као што је изражено, на пример, у релационој алгебри, су у L.
Сродне класе сложености
[уреди | уреди извор]L је подкласа NL, која је класа језика одлучивих у логаритамском простору на недетерминистичкој Тјуринговој машини. Проблем у NL може се трансформисати у проблем доступности чворова код усмереног графа који представља стања и промене стања недетермиинистичке машине, док границе логаритамског простора имплицирају да овај граф има полиномни број чворова и страница, из чега следи да је NL садржан у класи сложености P проблема који су решиви у детерминистичком полиномијалном времену.[4] Тако да важи L ⊆ NL ⊆ P. Чињеница да је L подскуп P се може доказати на други начин који је више директан: одлучивач који користи O(log n) простор не може користити више од 2O(log n) = nO(1) времена, јер је ово тотални број могућих конфигурација, L је такође сродан класи NC на следећи начин: NC1 ⊆ L ⊆ NL ⊆ NC², што значи да за дати паралелни компјутер C са полиномијалним бројем O(nk) процесора за неко константно k, сваки проблем који се може решити на C за O(log n) времена је у L, и сваки проблем у L се може решити у O(log² n) времена на C. Важни отворени проблеми укључују да ли је L = P,[2] and whether L = NL.[5].
Сродна класа проблема функција је FL. FL се често користи за дефинисање редукција у логаритамском простору.
Додатне особине
[уреди | уреди извор]L је ниско само за себе, зато што може да симулира пророчке упите из логаритамског простора ( грубо говорећи, „ позиви функција које користе логаритамски простор“) изнова користећи исти простор за сваки упит.
Остале примене
[уреди | уреди извор]Главна идеја коришћења логаритамског простора је то да се број са полиномијалном амплитудом може складиштити у логаритамском простору и користити за памћење показивача на позицији улаза.
Из овог разлога, класа у логаритамском простору је корисна за моделовање рачунарске обраде код које је улаз превише велик да би стао у оперативну меморију компјутера. Дугачки низови ДНК и базе података су добри примери проблема код којих ће само константан део улаза бити у оперативну меморији у датом времену и код којих имамо показиваче за обраду следећег дела улаза, користећи само логаритамску меморију.
Референце
[уреди | уреди извор]- ^ Sipser 1997, Definition 8.12. стр. 295.
- ^ а б Garey & Johnson 1979, стр. 177
- ^ See Garey & Johnson 1979, Theorem 7.13 (claim 2). стр. 179.
- ^ Sipser 1997, Corollary 8.21. стр. 299.
- ^ Sipser 1997, стр. 297; Garey & Johnson 1979, стр. 180